package algorithm.t202110;

import java.util.List;

/**
 * @author : 李红磊
 * @version :1.0
 * @date : 2021/10/25 10:13
 * @description :7道
 * 悲欢与爱恨。
 * persevere to last
 * 2021.10.25
 */
public class t20211025 {


    //240. 搜索二维矩阵|| 暴力dfs
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null) {
            return false;
        }

        boolean[][] visit = new boolean[matrix.length][matrix[0].length];//标记数组，用于记录是否已经访问过，不做无用功

        return dfs(matrix, target, 0, 0, visit);//从(0,0)开始深度遍历


    }

    private boolean dfs(int[][] matrix, int target, int x, int y, boolean[][] visit) {
        //若x，y不满足矩阵边界条件或者已经访问过，返回false
        if (x < 0 || x > matrix.length - 1 || y < 0 || y > matrix[0].length - 1 || visit[x][y]) {
            return false;
        }
        if (matrix[x][y] == target) {
            return true;
        }
        visit[x][y] = true;
        //从x，y的下右两条路线进行深度遍历，只要有其中一条能够找到目标元素，就视为该矩阵中存在此目标元素
        if (dfs(matrix, target, x + 1, y, visit) || dfs(matrix, target, x, y + 1, visit)) {
            return true;
        }

        return false;
    }

    //二分法
    public boolean searchMatrix2(int[][] matrix, int target) {
        if (matrix == null) {
            return false;
        }
        /*
            因为题目给定了关键字【有序数组】。即第一反应想到二分法。
            此解的思路为：对于该矩阵的每一行进行二分查找，若找到目标元素，则返回true，
                        若查找完所有行都未能找到目标元素，则表明此矩阵不含有目标元素，返回false

         */

        int rows = matrix.length, columns = matrix[0].length;

        for (int i = 0; i < rows; i++) {
            int left = 0, right = columns - 1;

            //从第一行进行二分查找
            //若该行的第一个元素都比目标元素大或者该行的最后一个元素都比目标元素小，则此行不需要进行二分了（目标元素不会存在此行），直接下一行
            if (matrix[i][left] > target || matrix[i][right] < target) {
                continue;
            }
            while (left <= right) {//对此行进行二分查找
                int mid = left + right >>> 1;
                if (matrix[i][mid] == target) {
                    return true;
                } else if (target > matrix[i][mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }

            }

            //若程序走到这，表面此行并没有找到目标元素。继续换下一行二分
        }

        //走到这，说明矩阵的所有行都没能找到目标元素
        return false;
    }


    //33.搜索旋转排序数组
    public int search(int[] nums, int target) {
        if (nums == null) {
            return -1;
        }

        if (nums.length == 1) {
            return nums[0] == target ? 0 : -1;
        }

        int left = 0, right = nums.length - 1;

        while (nums[left] > nums[right]) {
            right--;
        }
        if (right == nums.length - 1) {
            //表明此数组并未经过【旋转】，则只需要经过一次二分即可得出结果
            while (left <= right) {
                int mid = left + right >>> 1;

                if (nums[mid] == target) {
                    return mid;
                } else if (target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }

            }

        } else {
           /*
            表明此数组已经经过了【旋转】，所以我们将此数组分成两部分，
            例如：0,1,2,3,4,5,6,7 在下标为3出进行了【旋转】，旋转之后的数组成为：3,4,5,6,7,0,1,2。
                        而我们现在将旋转后的数组分为了 3,4,5,6,7 和 0,1,2 两部分，然后对着两部分分别进行二分

            */
            //先对right值进行备份，以便于第二部分的遍历
            int tempNum = right + 1;
            int len = nums.length - 1;
            //先对第一部分进行二分
            while (left <= right) {
                int mid = left + right >>> 1;
                if (nums[mid] == target) {
                    return mid;
                } else if (target > nums[mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }

            }
            //至此第一部分遍历完毕
            //遍历第二部分

            while (tempNum <= len) {
                int mid = tempNum + len >>> 1;
                if (nums[mid] == target) {
                    return mid;
                } else if (target > nums[mid]) {
                    tempNum = mid + 1;
                } else {
                    len = mid - 1;
                }

            }


        }

        return -1;
    }

    //74.搜索二维矩阵
    public boolean searchMatrix3(int[][] matrix, int target) {
        if (matrix == null) {
            return false;
        }

        boolean[][] visit = new boolean[matrix.length][matrix[0].length];//用于表面元素是否被访问过
        return dfs2(matrix, target, 0, 0, visit);
    }

    private boolean dfs2(int[][] matrix, int target, int x, int y, boolean[][] visit) {
        //边界判断
        if (x < 0 || x > matrix.length - 1 || y < 0 || y > matrix[0].length - 1 || visit[x][y]) {
            return false;
        }
        if (matrix[x][y] == target) {//若现在遍历到的元素就是目标元素，则返回true
            return true;
        }
        //否则将此元素记录到visit，表示已经访问过
        visit[x][y] = true;

        //继续向上下左右四个方向进行遍历，若其中有一条方向可以表返回true，表面此矩阵含有目标元素
        if (dfs2(matrix, target, x - 1, y, visit) || dfs2(matrix, target, x + 1, y, visit)
                || dfs2(matrix, target, x, y - 1, visit) || dfs2(matrix, target, x, y + 1, visit)) {
            return true;
        }

        return false;

    }

    public boolean searchMatrix4(int[][] matrix, int target) {
        if (matrix == null) {
            return false;
        }
        //题中说明了【每行中的整数从左到右按升序排列】，表面每一行都未递增有序数列，所以我们这里使用二分法。
        //通过对每一行进行二分查找，即可得出答案。
        int rows = matrix.length, columns = matrix[0].length;

        for (int i = 0; i < rows; i++) {
            //先判断此行是否值得二分查找
            if (target < matrix[i][0] || target > matrix[i][columns - 1]) {
                continue;//若目标值小于这一行的第一个元素或者大于这一行的最后一个元素，则此行不需要二分查找
            }
            int left = 0, right = columns - 1;

            while (left <= right) {
                int mid = left + right >>> 1;
                if (matrix[i][mid] == target) {
                    return true;//找到目标值，返回true
                } else if (target > matrix[i][mid]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            //程序走到这，表面此行没有找到目标元素，则进行下一行的二分查找
        }

        return false;
    }

    public boolean searchMatrix5(int[][] matrix, int target) {
        if (matrix == null) {
            return false;
        }
        /*
            由题我们可以得知：二维数组每一行从左至右一次递增，每一列从上而下也是递增，而且下面一行的第一个元素大于上一行的最后一个元素
            那么我们可以以二维数组的左下角为起点，建立直角坐标轴，然后进行查找

         */
        int rows = matrix.length, columns = matrix[0].length;
        for (int x = rows - 1, y = 0; x < rows && y < columns; ) {

            if (x < 0 || x > rows - 1 || y < 0 || y > columns - 1) {//边界条件
                break;
            } else if (matrix[x][y] == target) {//找到目标元素
                return true;
            } else if (target > matrix[x][y]) {//表明若矩阵含有目标元素，则其的下标一定是现在下标的右侧
                y++;
                continue;
            } else {//程序走到这，表示若矩阵含有目标元素，其下标在此行上方
                x--;
            }

        }
        return false;

    }

    //153.寻找旋转排序数组中的最小值
    public int findMin(int[] nums) {
        if (nums == null) {
            return -1;
        } else if (nums.length == 1) {
            return nums[0];
        }

        //找到旋转点
        int len = nums.length - 1;
        while (nums[0] > nums[len]) {
            len--;
        }
        if (len == nums.length - 1) {
            //表示该数组并未【旋转】，则直接返回第一个元素
            return nums[0];
        } else {
            //数组经过了【旋转】，则返回旋转点对应的元素
            return nums[len + 1];
        }

    }

    //162.寻找峰值
    public int findPeakElement(int[] nums) {
        if (nums == null) {
            return -1;
        } else if (nums.length == 1) {
            return 0;//如果数组中只有一个元素，那么这个元素就是该数组的峰值
        }
        int left = 0, right = nums.length - 1;

        /*
            题设给我们了：num[-1]=num[n]= -∞ ，意思就是我们只要是在【爬山】终将会有【山顶】，【山顶】就是我们要的峰值。
            例如：1，2，1，3，5，6，4 。 我们拿到1发现其右边的值为2，大于1，则视为我们正在【爬山】

         */

        while (left < right) {
            int mid = left + right >>> 1;

            if (nums[mid] <= nums[mid + 1]) {
                //正在【爬山】
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    //面试题08.05 递归乘法
    public int multiply(int A, int B) {
        int max = Math.max(A, B);
        int min = Math.min(A, B);

        int res = 0;
        for (int i = 0; min != 0; i++) {
            if ((min & 1) == 1) {
                res = res + (max << i);
            }
            min = min >> 1;
        }

        return res;
    }


    //面试题08.06 汉诺塔问题
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {

        int n = A.size();//得到盘子的总数
        move(n, A, B, C);

    }


    private void moveMy(int n, String A, String B, String C) {
        if (n == 1) {
            System.out.println(A + "移动到" + C);
        } else {
            moveMy(n - 1, A, C, B);
            System.out.println(A + "移动到" + C);
            moveMy(n - 1, B, A, C);

        }
    }


    private void move(int n, List<Integer> a, List<Integer> b, List<Integer> c) {
        if (n == 1) {
            c.add(0, a.remove(0));
            return;
        }
        move(n - 1, a, c, b);

        c.add(0, a.remove(0));
        move(n - 1, b, a, c);


    }


    public static void main(String[] args) {
        t20211025 t20211025 = new t20211025();


       /* int[][] tesArr = new int[3][3];
        tesArr[0][0] = 1;
        tesArr[0][1] = 4;
        tesArr[0][2] = 7;

        tesArr[1][0] = 2;
        tesArr[1][1] = 5;
        tesArr[1][2] = 8;

        tesArr[2][0] = 3;
        tesArr[2][1] = 6;
        tesArr[2][2] = 9;

        System.out.println(t20211025.searchMatrix2(tesArr, 1));*/


        t20211025.moveMy(3, "A", "B", "C");

    }


}
